package com.dbh.alg.datastructure;

/**
 * 删除链表倒数第n个节点
 * @author dongbanghui
 * @date 2025/5/9
 */
public class E03Leetcode19 {

    /**
     * 删除链表倒数第n个节点
     * @param head 链表头节点
     * @param n 倒数第n个节点
     * @return 删除后的链表头节点
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        recursion(s, n);
        return s.next;
    }

    /**
     * 递归删除链表倒数第n个节点
     * @param p 链表头节点
     * @param n 倒数第n个节点
     * @return 删除后的链表头节点
     */
    private static int recursion(ListNode p, int n) {
        if (p == null) {
            return 0;
        }
        int nth = recursion(p.next, n);
        if (nth == n) {
            p.next = p.next.next;
        }
        return nth + 1;
    }

    /**
     * 删除链表倒数第n个节点 - 快慢指针法
     *
     * @param head 链表头节点
     * @param n 倒数第n个节点
     * @return 删除后的链表头节点
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        ListNode fast = s;
        ListNode slow = s;
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return s.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1,2,3,4,5);
        ListNode o1 = removeNthFromEnd2(head, 2);
        System.out.println(o1);
    }
}
